package dynamicProgramming;

/**
 * @author zxc
 * @date 2023/01/28 15:15
 **/
/**
 * 题目 ：最长回文子串
 * 题目详述 ：
 * 给你一个字符串 s，找到 s 中最长的回文子串。
 * 如果字符串的反序与原始字符串相同，则该字符串称为回文字符串。
 *
 * 提示：
 * 1 <= s.length <= 1000
 * s 仅由数字和英文字母组成
 */
public class LongestPalindrome {
    /**
     * 思路 ：
     * 假设f(i，j)为字符串s中第i个字符到第j个字符所组成的子串是否为回文字符串;
     *
     * 状态转移方程 ：
     * 一般情况 ：（建立在字符串s长度 > 2的基础上）
     * （1）若是f(i,j)为回文字符串的话，f(i,j) = true;
     * （2）若是 f(i,j)不为回文字符串 && i > j 的话，f(i,j) = false;
     * ===> f(i,j) = f(i+1,j-1) && s[i+1] = s[j-1];
     * 特殊情况 ：（即，字符串s长度 <= 2情况）
     * （1）当字符串s长度为1的话（i == j），即其必然为回文字符串;
     * （2）当字符串s长度为2的话（i + 1 == j），当s[i] == s[j]时，其必然为回文字符串;
     * @param s
     * @return
     */
    public String longestPalindrome(String s) {
        int len = s.length();
        int begin = 0;
        int maxLength = 1;
        boolean[][] temp = new boolean[len][len];
        for(int i = 0; i < len; i++){
            // 特殊情况 ：若是字符串s的长度 <= 1的话，即字符串s本身就是回文字符串;
            temp[i][i] = true;
        }
        // 一般情况 ：
        // 遍历(长度 >= 2)的字符串子串;
        for (int l = 2 ; l <= len ; l++){
            // 所需要遍历子串的前一个索引;
            for(int i = 0 ; i <= len - l ; i++){
                // 所需要遍历子串的后一个索引
                int j = i + l - 1;
                // 若是字符串s中s[i] != s[j]时，即代表了子串S[i...j]不为回文字符串
                if(s.charAt(i) != s.charAt(j)){
                    temp[i][j] = false;
                }
                // 此处的else语句,代表了子串S[i...j]中的s[i] == s[j]情况;
                else {
                    // 即，当子串S[i...j]长度 <= 3的话，代表了子串S[i...j]为回文字符串;
//                    if(l <= 3){
                    if(l == 2){
                        temp[i][j] = true;
                    }
                    // 即，子串S[i...j]长度 >= 4情况;
                    else {
                        // 要求取temp[i][j]的话，所需要的是temp[i+1][j-1];
                        // 同时，遍历顺序 ：子串t长度逐步递增;
                        // 注意 ：temp[i][j]中所存储的是，长度为(j-i+1)的子串T[i...j]是否为回文字符串;
                        // 在T[i] == T[j]的情况下，取决于temp[i+1][j-1];(即，取决于更小的子串T[i+1...j-1]是否为回文字符串)
                        temp[i][j] = temp[i + 1][j - 1];
                    }
                }
                // 满足条件 ：
                // （1）temp[i][j]（即，起始下标为i && 结束下标为j）为回文子串;
                // （2）变量begin和maxLength所存储的回文子串长度 < 当前正在遍历的回文子串长度（满足子串是回文字符串的条件）
//                if(temp[i][j] && maxLength < l){
                if(temp[i][j]){
                    // 最长回文子串起始下标;
                    begin = i;
                    // 最长回文子串长度;
                    maxLength =  j - i + 1;
                }
            }
        }
        // 返回最长回文子串;
        // 需要注意的是，substring方法中所截取字符串的取值范围为[i,j);
        return s.substring(begin , begin + maxLength);
    }
}
